#include <stdlib.h>
#include <stdio.h>
#include <cmath>


typedef struct PrimeFactor 
{
    unsigned long prime;
    unsigned long power;
    struct PrimeFactor *next;
} PF;

PF *slist_prepend(PF *list, unsigned long prime, unsigned long power)
{
	PF* newlist;
    newlist=(PF*)malloc(sizeof(PF));
    newlist->prime=prime;
	newlist->power=power;
    newlist->next=list;
    return newlist;
}

PF *slist_append(PF *list, unsigned long prime, unsigned long power)
{
    PF* curlist;
	PF* newlist;
    newlist=(PF*)malloc(sizeof(PF));
    newlist->prime=prime;
	newlist->power=power;
	newlist->next=NULL;
	if(list==NULL)
	{
		list=newlist;
		return list;
	}
	curlist=list;
    while (curlist->next!=NULL)
    {
        curlist=curlist->next;
    }
    curlist->next=newlist;
    return list;
}


PF *slist_remove_all(PF *list, unsigned long power)
{
	int i;
	PF* curlist;
	PF* buflist;
	curlist=list;
	for(i=0; curlist->next!=NULL; i++)
	{
		while(curlist->power==power)
		{
			curlist=curlist->next;
			free(list);
			list=curlist;
			if(list==NULL)
			{
				return list;
			}
		}
		if(curlist->next==NULL)
		{
			return list;
		}
		if(curlist->next->power==power)
		{

			buflist=curlist->next;
			curlist->next=curlist->next->next;
			free(buflist);
		}
		if(curlist->next==NULL)
		{
			return list;
		}
		if(curlist->next->power!=power)
		{
			curlist=curlist->next;
		}
	}
	return list;
}


PF* SimpleNumbers(PF* multipliers , unsigned long n)
{
	unsigned long i, j, check, len, k;
	PF* buffer;
	len=0;
	k=sqrt(n);
	for(i=1; i<n; i++)
	{
		buffer = multipliers;
		check=0;
		for(j=1; (j<i-1) && ((buffer->prime)<k) && (j<len-1); j++)
		{ 
			if((i % ((buffer->next)->prime))==0)
			{
				check=1;
				break;
			}
			buffer = buffer->next;
		}
		if(check==0)
		{
			multipliers=slist_append(multipliers, i, 0);
			len++;
		}
	}
	return multipliers->next;
}

PF *prime_decompose(unsigned long n)
{
	unsigned long i;
	unsigned long len;
	PF *multipliers;
	PF *output;
	multipliers = (PF*)malloc(sizeof(PF));
	multipliers=NULL;
	multipliers = SimpleNumbers(multipliers, n);
	output=multipliers;
	while(multipliers->next!=NULL)
	{
		i=0;
		len=n;
		while(len % multipliers->prime == 0)
		{
			len = len / multipliers->prime;
			i++;
		}
		multipliers->power=i;
		multipliers=multipliers->next;
	}
	output=slist_remove_all(output, 0);
	return output;
}


void main()
{
	PF* output;
	unsigned int n;
	printf("Input number:\n");
	scanf("%ld", &n);
	output=prime_decompose(n);
	if(output==NULL)
	{
		printf("Simple number.\n");
	}
	while(output!=NULL)
	{
		printf("Multiplier - %d, power - %d.\n", output->prime, output->power);
		output=output->next;
	}
	system("PAUSE");
}